package com.Questions.DFS;


/**
 * 节点与其祖先之间的最大差值
 */
public class leetcode1026 {
    int max;
    public int maxAncestorDiff(TreeNode root) {
        // 每一个结点维护一个最大值和一个最小值 然后对比该结点的左子树和右子树
        // 计算出该节点和两个子树的差值 如果比现存的最大值大 那么更新
        max=0;
        maxAndMin(root,-1,Integer.MAX_VALUE);
        return max;
    }
    public int[] maxAndMin(TreeNode root,int Max,int Min){
        if(root==null){
            return new int[]{-1,Integer.MAX_VALUE};
        }
        int[] l=maxAndMin(root.left,Max,Min);
        int[] r=maxAndMin(root.right,Max,Min);
        Max=Math.max(l[0],r[0]);
        Min=Math.min(l[1],r[1]);
        Max=Math.max(Max,root.val);
        Min=Math.min(Min,root.val);
        if(l[0]!=-1){
            max=Math.max(Math.abs(root.val-l[0]),max);
            max=Math.max(Math.abs(root.val-l[1]),max);
        }
        if(r[0]!=-1){
            max=Math.max(Math.abs(root.val-r[0]),max);
            max=Math.max(Math.abs(root.val-r[1]),max);
        }
        return new int[]{Max,Min};
    }
}
